List all
partitions of the positive integer n into a sum of positive
integers. The partitions must satisfy the following conditions:
·
The summands in each partition are arranged in
non-increasing order.
·
All partitions are listed in lexicographical order.
Input. One positive
integer n (1 ≤ n ≤ 40).
Output. Print all valid
partitions, each on a separate line.
|
Sample
input |
Sample
output |
|
4 |
1 1 1 1 2 1 1 2 2 3 1 4 |
SOLUTION
combinatorics
Algorithm analysis
Let n = x1 + x2
+ … + xk be a partition of the number n
into natural summands. According to the problem statement, the summands in any
partition must satisfy the inequality:
x1 ³ x2
³ … ³ xk
The
first summand x1 can take values from 1 to n,
and each subsequent xi
(2 £ i
£ k)
can take values from 1 to xi-1.
The
recursive idea behind the partition generation procedure is as follows: if,
when partitioning the number n, the first summand x1 (x1 £ n)
is chosen, then one should recursively generate all possible partitions of the
number n – x1
into summands that do not exceed x1.
We’ll
use the array x to generate the partitions of the number n.
int x[50];
The
function f generates
the partitions of the number n and takes three arguments:
·
pos – the
current position in the array x;
·
max – the
maximum allowed value of the summand that can be placed at position pos;
·
n – the
current value of the number to be partitioned.
void f(int pos, int max, int n)
{
If the value of n becomes zero, it means the partition is complete,
and the current contents of the array x represent one of the partitions.
In this case, we print the array.
if (n ==
0)
{
for (int i =
0; i < pos; i++)
printf("%d
", x[i]);
printf("\n");
return;
}
At position pos of the array x, any number from 1 to min(max, n) can be placed.
for (int i =
1; i <= min(max, n);
i++)
{
x[pos] =
i;
f(pos + 1,
i, n - i);
}
}
The main part of the program. Read the input value n and start the
function to generate all possible partitions of this number.
scanf("%d",&n);
f(0,n,n);